#include <bits/stdc++.h>

using namespace std;

// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/

class Solution 
{
public:
    // 辅助数组的解法（不是最优解）
	// 时间复杂度 O(n)，额外空间复杂度 O(n)
    int trap1(vector<int>& height) 
    {
        int n = height.size(), lmax[n], rmax[n];
        lmax[0] = height[0];
        for(int i = 1; i < n; ++i) lmax[i] = max(height[i], lmax[i - 1]);
        rmax[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; --i) rmax[i] = max(height[i], rmax[i + 1]);

        int ans = 0;
        for(int i = 1; i < n - 1; ++i)
        {
            ans += max(0, min(lmax[i - 1], rmax[i + 1]) - height[i]);
        }
        return ans;
    }

    int trap2(vector<int>& height) 
    {
        int n = height.size(), preMax[n], sufMax[n];
        preMax[0] = height[0];
        for(int i = 1; i < n; ++i)
        {
            preMax[i] = max(preMax[i - 1], height[i]);
        }

        sufMax[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; --i)
        {
            sufMax[i] = max(sufMax[i + 1], height[i]);
        }

        int ret = 0;
        for(int i = 1; i < n - 1; ++i) ret += min(preMax[i], sufMax[i]) - height[i];
        return ret;
    }

	// 双指针的解法（最优解）
	// 时间复杂度 O(n)，额外空间复杂度 O(1)
    int trap3(vector<int>& height) 
    {
        int n = height.size(), lmax = height[0], rmax = height[n - 1];
        int ans = 0, l = 1, r = n - 2;
        while(l <= r)
        {
            if(lmax <= rmax)
            {
                ans += max(0, lmax - height[l]);
                lmax = max(lmax, height[l++]);
            }
            else
            {
                ans += max(0, rmax - height[r]);
                rmax = max(rmax, height[r--]);
            }
        }
        return ans;
    }
};